1. Field of the Invention
This invention relates generally to detection, demodulation and decoding of digital information in data storage and/or communication systems, and to the efficient implementation of such circuits. More particularly, the invention relates to sequence-based demodulation of partial-response signals and to sequence-based decoding of convolutional codes using a Viterbi-like algorithm.
2. Prior Art
In the storage or transmission of digital information, the bits or symbols of the user data are actually transmitted or stored via a physical medium or mechanism whose responses are essentially analog in nature. The analog write or transmit signal going into the storage/transmission medium or channel is typically modulated by channel bits that are an encoded version of the original user-data bits. The analog read or receive signal coming from the medium is demodulated to detect or extract estimated channel bits, which are then decoded into estimated user-data bits. Ideally, the estimated user-data bits would be an identical copy of the original user-data bits. In practice, they can be corrupted by distortion, timing variations, noise and flaws in the medium and in the write/transmit and read/receive channels.
The process of demodulating the analog read signal into a stream of estimated user-data bits can be implemented digitally. Digital demodulation in advanced mass storage systems requires that the analog read signal be sampled at a rate that is on the order of the channel-bit rate. Maximum-likelihood (ML) demodulation is a process of constructing a best estimate of the channel bits that were written based on digitized samples captured from the analog read signal.
FIG. 1 shows an exemplary read signal 100, which is a positive-going pulse generated by an inductive read head, for example, from a single medium transition such as transition 103 from North-South to South-North magnetization of track 104 on a rotating disk. Typically, the write signal modulates a transition in the state of the medium to write a channel bit of 1 and modulates the absence of a medium transition to write a 0 channel bit. Thus, transition 103 corresponds to a single channel bit of value 1 in a stream of 0's.
It is common to use run-length-limited (RLL) encoding of the original user data bits, which are arbitrary or unconstrained, into an RLL-encoded stream of channel bits. It may be desirable that there be no less than d zeroes between ones; that is, that the medium transitions be spaced by at least d+1 bit times. This constraint can help keep to a manageable level the interference effects among the pulses in the analog read signal. On the other hand, because medium transitions provide timing information that must be extracted from the read signal to ensure synchronization of the demodulator with the pulses in the read signal, it may be desirable that there be no more than k zeroes between ones; that is, that there be a medium transition at least every k'th bit time. An RLL(d,k) code is a code that can encode an arbitrary stream of original user-data bits into a stream of channel bits such that the encoded channel bit stream satisfies these two constraints.
For example, the following table shows a commonly used RLL(2,7) code:
______________________________________ User Data Bits RLL(2,7)-Encoded Channel Bits ______________________________________ 000 000100 0010 00100100 0011 00001000 010 100100 011 001000 10 0100 11 1000 ______________________________________
Note that this RLL(2,7) code requires that the information bit rate available for channel bits be twice the bit rate provided for user-data bits. Other RLL codes enforce the constraint that d=1 (i.e. that no adjacent channel bits both be 1). RLL(l,k) encoding is also called one-constraint encoding, or encoding with a minimum run length of 1.
In FIG. 1, sample set 101 shows the values of four samples in the case of side sampling of read signal 100; i.e. 0.333, 1.0, 1.0, and 0.333. Sample set 101 is equivalent to the set 1, 3, 3, 1; that is, only the ratios among samples are significant. A signal model gives rise to an expected sample sequence for a single or isolated transition in medium state. Typically, only a few samples of the response to an isolated medium transition are non-zero; in this case, four are non-zero. In a side-sampled signal model such as 1, 3, 3, 1, timing circuitry in the demodulator attempts to maintain a lock on the incoming signal such that there are two adjacent samples on opposite sides of the peak of an isolated pulse. Other sample timing arrangements may be useful. In center sampling, the timing circuitry trys to lock the sample times to the read signal pulses such that one sample occurs at the peak of each pulse. Sample set 102 shows the values of four samples in the case of center sampling of a similar read signal 105; i e. 0.5, 1.0, 0.5, and 0.0 (or 1.0, 2.0, 1.0 and 0.0 depending on the arbitrary normalization used). An expected sample sequence of 1, 2, 1 corresponds to the signal model known in the prior art as Extended Partial-Response Class IV (EPR4).
Such sample sequences are samples of a continuous-time analog read-signal waveform such as may be produced in the receiver of a communications system or in the readback circuitry of a storage device. For a system that is bandwidth limited to 1/(2T), where T is the sample spacing in time, the sampling theorem declares that the continuous time waveform must be a superposition of sinc functions (sinc(x) is defined as sin(x)/x for x&lt;&gt;0, and as 1 for x=0), with one sinc function centered at each sample point and of amplitude equal to that sample value and with zero crossings at all other sample points. As an example, in saturation magnetic recording, the current in an inductive write head takes on values of +I and -I. The basic excitation applied to the recording channel is a step in current from +I to -I, or vice versa, in the analog write signal. This step in write current produces a transition in the magnetization state of the medium as it moves past the head. When an inductive read head is passed over this magnetic medium transition, a voltage pulse is induced by the bandwidth limited differentiating interaction of the head with the magnetization of the medium. By suitable filtering or equalization, the sequence of samples on an isolated transition response pulse can be made to be {..., 0, 0, 1, 2, 1, 0, 0, ...}, in which case the recording or transmission channel matches the EPR4 signal model.
Another sample sequence well known in the prior art is the Partial Response Class IV signal model (PR4), which corresponds to an expected sample sequence of 0, 1, 1, 0. There are numerous other known signal models. Further, as one is designing or taking measurements on a write/medium/read channel, it may be desirable to take into account the exact response, noise and distortion characteristics of the channel in selecting the signal model to be implemented in the demodulator. Thus, there is a need for a demodulator that is programmable as to the signal model, or expected sequence of sample values for an isolated medium transition.
In data storage it sometimes happens that a data record is not read correctly on the first attempt. Such an event is usually detected by an error detection scheme, but it may not be possible to correct the error(s). In that event the only hope of recovering the data is to attempt another read of the data record. On second and subsequent reads (i.e. on retrys) it may be desirable to change some parameters of the read circuitry in the hopes that such changes will suppress or attenuate the error mechanism. Thus there is need for read-channel electronics that can be easily changed for retries. Additionally, in the case of data storage on rotating disks, the constant angular velocity of the disk results in a variable velocity of the recording medium with respect to the read and write heads. Even if zones are used, in which the channel bit rate varies among zones as the heads move in and out on the disk, there is still a variation in signal shape within each zone from its innermost track to its outermost track. Thus there is a need for read-channel electronics that can be easily changed to accommodate changes in system characteristics.
In situations such as mass information storage in magnetic media, significant storage-system speed and capacity gains can be realized if the information bits can be closer together in position/time on the medium. However, according to information theory the sample rate must be at least as high as the channel bit rate to utilize all available channel capacity. More precisely, the Nyquist sampling criterion requires that the sample frequency be at least twice the highest frequency contained in the signal, or else information is lost due to aliasing. This information loss could be prevented by introducing redundancy through appropriate coding, but this would reduce the channel capacity for user information. All the partial response signal models described herein may contain frequencies up to one-half of the channel bit rate, implying that the sample rate must be no less than the channel bit rate to avoid aliasing. Sampling at exactly the channel bit rate satisfies the Nyquist criterion when the sample times are appropriately synchronized with the signal. Sampling at the channel bit rate is also convenient for synchronization of the demodulator circuits because the demodulator then produces one estimated channel bit per sample.
Therefore, at least one sample of the analog read signal is typically required per channel bit that is to be demodulated from the signal. Digital decoders are typically complex circuits and may require a slower processing or clock rate than can be supported by analog-to-digital converters and simple buffers. Thus, there is a need for demodulator circuitry that can process in real time read-signal samples that are taken at a higher sampling rate than the processing rate of the demodulator itself.
Further, as medium transitions are more closely positioned, the writing and reading processes become more sensitive to the distortion, timing variations and noise that are inevitably introduced in the processes of writing, storing, and reading. Also, as the transitions become closer, the ability of the medium to fully transition from, say, North-South magnetization to South-North magnetization may be taxed. Also, as the medium transitions become closer, interference effects increase among adjacent or nearby transitions.
FIG. 2 shows how positive-going pulse 200 from first medium transition 201 combines with negative-going pulse 202 from second transition 203 to produce analog read signal 204, which can be viewed as the interference of the two pulses. Adjacent medium transitions always give rise to read pulses of opposite polarities because they always are created by transitions of opposite types, for example North-South changes to South-North in transition 201, so adjacent transition 202 must be South-North changing back to North-South. Read signal 204 might give rise to a sequence of samples such as 0.333, 1.0, 0.667, -0.667, -1.0, -0.333. To the extent that the read process is linear (and it may not be entirely linear), the voltage waveform induced in the read head will be the superposition of a sequence of pulses, where each pulse is the response to an isolated magnetic transition on the medium.
Clearly, engineering a high-performance digital demodulator is a complex challenge given the combined effects of the limited sampling rate in a digital demodulator, possibly incomplete transitions in the medium, interference among read-signal responses to medium transitions, and distortion, timing variations, noise and flaws in the medium and in the write and read channels.
The prior art uses a method known as partial-response signaling to increase medium transition rates. Partial-response signaling is described in the book "Digital Transmission of Information", by Richard E. Blahut, 1990, pp. 139-158 and 249-255. This method allows the analog response of the storage/transmission medium and of the write/transmit and read/receive circuitry to a medium transition to overlap with the response to adjacent transitions associated with subsequent information bits. If properly implemented, this method can achieve higher information bit rates/densities than the alternative of requiring the medium transitions to be spaced such that the read signal responses do not overlap significantly. A sequence demodulator is required for partial-response signaling.
The prior art uses the Viterbi algorithm to implement sequence detectors, including demodulators and decoders. The Viterbi algorithm is described in the book "Fast Algorithms for Digital Signal Processing", by Richard E. Blahut, 1985, pp. 387-399. A Viterbi demodulator does not attempt to decide whether or not a medium transition has occurred immediately upon receipt of the sample(s) that correspond to that transition. Rather, as samples are taken from the analog read signal, the Viterbi demodulator keeps a running tally of the error between the actual sample sequence and the sample sequence that would be expected if the medium had been written with a particular sequence of transitions. Such an error tally is simultaneously kept for several possible transition sequences. As more samples are taken, less likely choices for transition sequences are pruned from consideration. If the set of possible sequences of medium transitions is appropriately constrained, then the location of each medium transition becomes known with a high degree of likelihood within a reasonable time after taking the samples corresponding to that transition. This effect is shown in FIG. 5, which illustrates the deferred decision making of a particular Viterbi demodulator in the case of a particular actual sample sequence by showing how the contents of the path memories evolve as additional read-signal samples are taken. A path memory of a sequence demodulator stores information concerning a particular sequence of transitions that is currently being considered as a candidate for the correct transition sequence.
Two of the most significant decisions in designing a modulator and corresponding demodulator are the choice of encoding constraints and the choice of signal models. The encoding constraints chosen may affect the complexity of the demodulator. The filtering and sampling strategy used in the read/receive/demodulate processes can be designed to generate a pulse response to an isolated medium transition that corresponds with the signal model chosen. A sample sequence model is a particular finite-state machine, where the states and transitions of the finite-state machine are determined by the encoding constraints and the signal model chosen. A sequence of expected read-signal samples can be viewed as being generated by a sample sequence model. Viterbi demodulators keep track of one error tally per state in the sample sequence model.
FIG. 3 shows the sample sequence model for a stream of RLL(1,infinity) encoded channel bits as viewed by a demodulator that uses the EPR4 signal model. Each sequence-model transition is represented in FIG. 3 by an arrow labeled both with the expected values for the associated read-signal sample and with the current RLL-encoded channel bit that generated the current medium transition, or lack thereof, in the write/transmit/modulate process. For example, sequence-model transition 301 is labeled with expected sample value 302 (+0.5) and with estimated channel bit value 303 (1). Transition 301 occurs upon taking the sample that shows the leading edge of the positive-going read-signal pulse associated with an isolated medium transition, as might be produced for example in the case of a magnetic medium transition from North-South magnetization to South-North magnetization. Each sequence-model state is represented in FIG. 3 by a circle which, as an aid to understanding, is labeled with a sequence of 3 digits (0 for North and 1 for South) corresponding with the current medium state and the medium states associated with the previous two samples (from right to left). Accordingly, sequence-model transition 301 is the transition from state 000 (or North, North, North) to state 001 (or North, North, South). Note that these state labels do not directly correspond to the sequence of channel bits. Often the sequence-model states are referred to by the decimal equivalents of the state labels used in FIG. 3 as interpreted as three bit binary numbers. All possible sequences of EPR4 signals that can be read from medium written with an RLL constraint of d=1 may be generated by traversing the state diagram of this sample sequence model.
In general, the number of states in a sample sequence model without RLL constraints is 2 N, where N is the number of samples between the first and last nonzero samples (inclusive) of the system response to its basic excitation. The imposition of coding constraints, such as RLL constraints or other codes mapping from user-data bits to channel bits, may change the number of states and transitions between states. For example, in the case of FIG. 3, because of the RLL constraint of d=1 chosen, the 010 and 101 states are impossible or prohibited states. To take another case, an RLL constraint of k=7 that is incorporated into the sample sequence model may increase the number of sequence-model states. If each sequence-model transition is assumed to occur with some specified probability, then a sample sequence model is equivalent to a Markov model for a source of expected samples.
The labels on the sequence-model transitions shown in FIG. 3 associate the presence (estimated channel bit value of 1) or absence (estimated channel bit value of 0) of a medium transition with the sample where the corresponding read-signal response first appears. There are other ways to associate the estimated channel bits to be output with the sequence-model transitions, e.g. the 1 values could appear on sequence-model transitions that correspond to the peak of the read-signal response.
To understand this sample sequence model, consider a simple decoder for an ideal read signal without noise, distortion or timing variations that is implemented according to the state machine of FIG. 3. This decoder makes one state transition per each sample of the read signal. Assume that this decoder is currently in state 000 (corresponding to a medium sequence of North-South, North-South, North-South, or NNN) and the demodulator receives a sample value of +0.5. This sample indicates the leading edge of a medium transition from North-South magnetization to South-North magnetization. This results in a next state of 001 (or NNS) and a demodulator output or estimated channel bit of 1, which indicates the presence of this medium transition. Because of the one-constraint encoding, the only sample that can be expected to occur next is +1.0, which is the sample that is aligned with the center of the read-signal pulse due to this medium transition. This sample results in a next state of 011 (or NSS) and a demodulator output of 0, which indicates that another medium-transition response does not start with this sample. Because we have now satisfied the run-length constraint, the next sample may or may not be affected by the leading edge of a pulse due to a second medium transition. Thus state 011 has two possible transitions leading from it. If a second medium-transition pulse is starting with the next sample, then the +0.5 trailing sample that must be present due to the first transition would be offset by the -0.5 leading sample of the second medium transition, and the expected sample would be 0.0. Therefore, receiving a sample value of 0.0 results in a next state of 110 (SSN), and an estimated channel bit of 1 to indicate the second medium transition. Alternatively, receiving a sample value of +0.5 indicates that there is not yet another medium transition and results in a next state of 111 (SSS) and a demodulator output of 0. If the state machine is in state 111, then receiving a sample of 0.0 results in a next state of 111 and an output of 0, i.e. no new medium transition. The remaining transitions and states are symmetrical with those in the above description. Given an ideal set of samples, the output of a demodulator that directly implements this state machine would exactly reproduce the channel bits written to the medium.
In operation, a Viterbi demodulator can be thought of as walking the trellis formed by taking each state of a sample sequence model over each sample time. FIG. 4 shows the fundamental frame of the trellis of the EPR4 state machine shown in FIG. 3 between time T and time T+1. Each possible transition of the EPR4 state machine is represented as a branch in the trellis frame. Let S(T) be the read-signal sample taken at time T. Let the branch error metric of, for example, the branch from state 001 to 011, be the quantity (S(T)-1.0) squared, because +1.0 is the expected sample value for that branch. Because there is only one sequence-model transition leading into state 011, the path error for state 001 at time T, plus this branch error metric and the associated estimated channel bit is always 0. To take a second example, state 001 could be reached at time T+1 either from state 000 with a channel bit of 1 and an expected sample of +0.5 or it could be reached from state 100 with a channel bit of 1 and an expected sample of 0.0. So for state 001, both branch error metrics are computed, i.e. the quantity (S(T)-0.5) 2 and S(T) 2. The first branch error metric is added to the path error metric for state 000 at time T, and the second branch error metric is added to the path error metric for state 100 at time T. The Viterbi algorithm then compares these two metrics and the path with the smallest distance from the actual sample sequence is selected as indicating the most likely path along which state 001 might be entered at time T+1.
For each sample time, the expected sample for each possible state-machine transition, or trellis branch, is compared with the read-signal sample to generate an error metric for that branch. This branch error metric is accumulated over multiple sample times, thus forming a path error metric. A Euclidean distance metric may be used; i.e. a branch error is the square of the difference between the actual read-signal value and the expected value for that state transition at that sample time. A Euclidean path error would be the square root of the sum of the branch errors along that path, but since only comparisons among path error metrics are significant, there is no need to compute a square root and the sum of the branch errors may be used as the path error metric. Other error metrics may be used, for example the absolute value of the difference between the actual sample and the expected sample. For each state at each sample time, the history of possible paths that may have led to that state is reduced by assuming that the state was entered by that path leading into it that has the lowest path metric. This simplification is justified by the fact that no future samples will shed any further light on which path may have led up to that state at that time. As an example of this calculation, state 000 in FIG. 3 could be entered from either itself or from state 100. In the former case, the expected sample would be 0.0 and in the latter it would be -0.5. At each sample time, the current sample is compared with each of these expected sample values. Let S be the current sample and P(X) the current path error metric associated with state X. If (S+0.5) 2+P(100) is less than (S-0.0) 2+P(000), then the Viterbi algorithm considers that state 000 would be entered from state 100 at this time and not from the loop from itself. A similar computation is performed for each state at each sample time.
At any sample time, the state that currently has the minimum path error metric could be taken as the correct state and the estimated channel bit could be taken directly from the sequence-model transition corresponding to the chosen branch into that state. But instead, the Viterbi demodulator, like other sequence demodulators, defers this decision until a sequence of subsequent samples has been taken. No attempt is made to determine which state correctly models the channel bit sequence written into the medium at the corresponding write times. Rather, the pruning of unlikely past possibilities occurs only within each state for each sample. Thus, path histories of estimated channel bits must be kept for each state in the sample sequence model. If the modulator and demodulator are designed appropriately for the characteristics of the medium and the read and write channels, then after a reasonable number of samples beyond sample T, the path histories associated with all of the sequence-model states are very likely to make the same estimate of the value of the channel bit corresponding to sample T.
FIG. 5 illustrates the deferred decisions that a Viterbi demodulator makes. This figure was generated by a software implementation of a particular Viterbi demodulator operating on a particular actual sample sequence. Signal 501 represents a digitally sampled ideal read signal without noise, distortion or timing variations. Trellis path 502 is the correct path, i.e. it corresponds to the written channel bits and to ideal read signal 501. Signal 503 is a noise signal that is added to signal 501 to produce actual sample sequence 504. Trellis 506 shows the paths contained in the path memory, after the 10th sample has been taken, for each of the 8 states of the particular sample sequence model used in this figure. Note that after the 10th sample, each path estimates the same sequence-model state corresponding to the 1st through the 5th samples, but that after the 5th sample, the contents of the path memories diverge in order to find the most likely path into the state that they represent at the 10th sample time. Trellis drawings 507-510 show the paths contained in all path memories as of the 11th through the 14th sample time respectively. In each of trellis drawings 506-510, the path histories associated with all of the sequence-model states make the same estimate of all channel bits up to a reasonably recent time, i.e. between 3 to 5 samples prior to the current sample.
In a mathematical sense, the maximum-likelihood decision rule says to choose as the estimate of the written channel bit sequence that sequence, out of all possible channel bit sequences, for which the conditional probability of receiving the actual sample sequence is highest. A Viterbi demodulator sampling the analog read signal at the channel bit rate satisfies this maximum-likelihood criterion if the analog read signal contains white Gaussian noise added to the expected read-signal pulse samples and the analog read signal is passed through a filter with a frequency response matched to the channel.
For each state in the sample sequence model, the path histories of estimated channel bits are kept in a path memory. The path memory in a sequence detector stores the information necessary to define each surviving path in the trellis. In a prior-art Viterbi detector, there is one surviving path for each state of the source model. The information in the path memory may be encoded and managed in a variety of ways. One way is to simply store the sequence of decisions from each ACS module regarding which of its input paths was chosen at each iteration. In this case the path memory amounts to a set of shift registers, and some means must be provided to trace the paths back through the trellis to determine the estimated channel bit sequence that is the primary output of the demodulator. The length of the path memory is the number of frames back through the trellis for which each surviving path can be reconstructed, counting the current frame. In well-designed detectors, there is a high probability that the surviving paths will all emanate from the same sequence-model state at some point in the trellis within the length of the path memory, and thus share a common path before that point. When this is so, any one of the surviving paths may be traced back to determine the demodulator's estimated channel bit output associated with the oldest frame in the path memory.
In practice, a path memory of 6 to 30 bits may be sufficient. That is, it may be large enough to ensure that there is a high probability that the channel bits are identical in each state's path memory for the bits at the least-recent end of each path memory. Path memory requirements depend on the signal model and on the coding constraints applied. For example, a lower value for k in the RLL(d,k) constraints on the channel bits can in some cases lower the length of the path memory required because the occurrence of medium transitions tends to force or expedite the Viterbi algorithm to make significant decisions.
Path memories can be burdensome to implement. Thus there is a need for techniques to reduce the number of path memories required to implement a Viterbi-like algorithm.
In typical prior-art implementations of the Viterbi algorithm, the signed add, square, add, compare and select computation described above is performed for each sequence-model state. The results of the signed add and square computation may be the branch error metric for more than one branch. In this case, the output of some of the modules that implement the computation of the branch error metrics may be used as inputs to more than one add, compare, select (ACS) module. For example, FIG. 6 is a block diagram of an implementation of these steps for the EPR4 d=1 sample sequence model, which is shown in FIG. 3. Branch error metric generators 600-604 implement the signed add and square computation for each of the possible values of expected samples, i..e. -1.0, -0.5, 0, +0.5, and +1.0). ACS modules 605, 606, 608, and 609 implement the add, compare, and select computation for states 000, 001, 111, and 110 respectively. Each also stores the current path error metric for the best path, at any given time, into the state it represents. They also communicate, via selection indicator lines 611-614 respectively, to path memories 615 which of the two possible input transitions they have selected as the most likely path into the state they represent. A more detailed block diagram of the implementation of two-input ACS modules 605, 606, 608, and 609 is shown in FIG. 7. Modules 607 and 610 are ACS modules for the special case of states 011 and 100 which have only one sequence-model transition leading into them. Modules 607 and 610 implement the add and store-path-error-metric functions only. In this prior-art Viterbi demodulator implementation, one ACS module is required for each state in the sample sequence model. ACS modules can be burdensome to implement.
As more samples are taken per each medium transition response and as larger amounts of interference are allowed among pulses in the read signal, more states are required in the sample sequence model. Thus there is a need for a technique that reduces the number of ACS modules required to implement a Viterbi-like algorithm.
Consider the following actual sample sequence: 0.0, 0.25, 0.75, 0.75, 0.25, 0.0 in the d=1 EPR4 partial-response model described above. The trellis diagram shown in FIG. 8 shows two paths that could equally well, or equally poorly, have generated such a sequence of samples (there are other such paths: the two paths shown assume that state 000 was the initial state). The channel bit sequences associated with these two paths are 010000 and 001000. They differ by one bit time in terms of where the medium transition occurs. The expected sample sequence associated with the first of these two paths is 0.0, 0.5, 1.0, 0.5, 0.0, 0.0, while the expected sample sequence for the second path is 0.0, 0.0, 0.5, 1.0, 0.5, 0.0. The squared Euclidean metric for each path may be computed for a given actual sample sequence by summing the squares of the differences between the actual sample sequence and each expected sample sequence. The result is that each path arrives in state 111 at time T+5 with a squared path metric of 0.25 . This represents a case where the actual sample sequence lies on a decision boundary, and some arbitrary choice must be made between the two paths. More commonly, the sample values will favor one path over the others, for example an actual sample sequence of 0.0, 0.26, 0.75, 0.75, and 0.24 favors the channel-bit sequence of 010000 with its squared path metric of 0.2402, over the channel-bit sequence of 001000 with its squared path metric of 0.2602.
If one of the paths in FIG. 8 is the correct path, i.e. the path representing the sequence-model transitions that correspond to the sequence of written channel bits, then the other path is an error path. The selection by the demodulator of the error path instead of the correct path would constitute an actual error event, and would result in one or more erroneous estimated channel bits being output from the demodulator. The example of FIG. 8 is a closed potential error event beginning at time T+1 and ending at time T+5 because the erroneous path and the correct path converge to the same state at time T+5. In contrast, it would be an open potential error event if the trellis ended at time T+4, before the paths had merged.
More generally, any path through the trellis may be the correct path and any pair of paths in the trellis constitutes a potential error event as long as they begin in the same state. A potential error event is any two paths in the trellis that begin in the same state and diverge in their second state. The beginning of a potential error event is the point where any two paths diverge. A codeword is the expected sample sequence associated with a particular trellis path.
The distance of a potential error event is the distance between the codewords of the two paths of the potential error event. Using the Euclidean metric, the square of this distance is equal to the path error metric that would be built up in the error path if the actual sample sequence corresponded to the ideal sequence for the correct path. The minimum distance for a given signal model is defined as the minimum distance of any closed potential error event or the minimum distance of any open potential error event of duration greater than the path length, whichever is smaller. Since the error rate of the demodulator decreases with increased minimum distance, one is motivated to choose, if possible, a path length sufficient to contain all open error events whose distance is less than the minimum distance of closed potential error events. These considerations are analogous to Hamming distance properties of error correction codes.
At relatively low bit error rates, the performance of a Viterbi demodulator is almost entirely determined by the minimum distance and by the signal-to-noise ratio. Actual error events of distance larger than the minimum distance are quite improbable compared with the minimum distance events and may safely be ignored in the design of the demodulator without seriously affecting the bit error rate. Thus there is a need for a technique that reduces the implementation complexity of the Viterbi algorithm without sacrificing its ability to handle minimum distance error events.